package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/smallest-string-starting-from-leaf/
 * <p>
 * 给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
 * <p>
 * 返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
 * <p>
 * 注：字符串中任何较短的前缀在 字典序上 都是 较小 的：
 * <p>
 * 例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。
 * 节点的叶节点是没有子节点的节点。
 *
 * @author hanjuntao
 * @date 2025/9/2 0002
 */
public class L_988_从叶节点开始的最小字符串 {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);

        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(4);

        System.out.println(smallestFromLeaf(root));
    }

    /**
     * 思路（使用辅助）：
     *
     * 1. 获取树的所有路径，存储到一个list中
     * 2. 对list进行排序
     * 3. 返回第一个路径
     *
     *
     * @param root
     * @return
     */
    public static String smallestFromLeaf(TreeNode root) {
        if (root == null) {
            return "";
        }
        List<String> result = new ArrayList<>();

        dfs(root, "", result);

        result.sort(String::compareTo);
        return result.get(0);
    }

    private static void dfs(TreeNode root, String s, List<String> result) {
        if (root == null) {
            return;
        }

        if (s.isEmpty()) {
            s = String.valueOf(getChar(root.val));
        } else {
            s = getChar(root.val) + s;
        }

        if (root.left == null && root.right == null) {
            result.add(s);
        }
        dfs(root.left, s, result);
        dfs(root.right, s, result);
    }

    private static char getChar(int val) {
        if (val >= 0 && val <= 25) {
            return (char) ('a' + val);
        }

        return ' ';
    }
}
